package leetcode_core.leetcode_3;

import java.util.*;

public class OpenLock {
    public int openLock(String[] deadends, String target) {
        int depth = 0;
        Queue<String> q = new LinkedList<>();
        Set<String> book = new HashSet<>();
        String root = "0000";
        q.add(root);book.add(root);
        Set<String> deads = new HashSet<>(Arrays.asList(deadends));
        while (!q.isEmpty()){
            int size = q.size();
            for(int j = 0 ;j<size;j++){
                String head = q.poll();
                if(deads.contains(head)){
                    continue;
                }
                if(head.equals(target)){
                    return depth;
                }
                for(int i = 0;i<4;i++){
                    String plusOne = plusOne(head, i);
                    if(!book.contains(plusOne)){
                        q.offer(plusOne);
                        book.add(plusOne);
                    }
                    String minusOne = minusOne(head, i);
                    if(!book.contains(minusOne)){
                        q.offer(minusOne);
                        book.add(minusOne);
                    }
                }
            }
            depth++;
        }
        return -1;
    }


    private String plusOne(String value,int i){
        //向上转
        char[] chars = value.toCharArray();
        if(chars[i] == '9'){
            chars[i] = '0';
        }else{
            chars[i]++;
        }
        return new String(chars);
    }

    private String minusOne(String value,int i){
        //向下转
        char[] chars = value.toCharArray();
        if(chars[i] == '0'){
            chars[i] = '9';
        }else{
            chars[i]--;
        }
        return new String(chars);
    }


}
